package main

import (
	"strconv"
	"strings"
)

/*
控制流程
只出现一次的数字：给定一个非空整数数组，除了某个元素只出现一次以外，
其余每个元素均出现两次。找出那个只出现了一次的元素。可以使用 for 循环遍历数组，结合 if 条件判断和 map 数据结构来解决，
例如通过 map 记录每个元素出现的次数，然后再遍历 map 找到出现次数为1的元素。
*/
func TaskOne(currentList []int) int {
	var numberMap = make(map[int]int)
	for _, value := range currentList {
		numberMap[value]++
	}
	result := -1
	for key, value := range numberMap {
		if value == 1 {
			result = key
		}
	}
	return result

}

/*
回文数

考察：数字操作、条件判断
题目：判断一个整数是否是回文数

就是“正着读和反着读完全一致”的一串字符。
中文： 上海自来水来自海上 、 人人为我，我为人人
英文： level 、 racecar

是回文数： 121 、 12321 、 0
不是回文数： -121 （带负号）、 10 （倒过来是 01，即 1，和 10 不同

思路

循环开始： x > rev  成立（12321 > 0
轮次
执行语句                    现场发生了什么（十进制视角）   结果（x        rev）
1 rev = 0*10 + 12321%10    取个位 1，rev 变成 1           1232        1

	x /= 10                  把 12321 的个位砍掉

2 rev = 1*10 + 1232%10     取个位  2，rev 变成 12         123         12

	x /= 10                   砍掉个位

3  rev = 12*10 + 123%10    取个位 3，rev 变成 123        12           123

现在  x <= rev （12 ≤ 123），循环结束。
*/
func TaskTwo(x int) bool {

	// 负数、以及以 0 结尾的非 0 数，直接排除
	if x < 0 || (x%10 == 0 && x != 0) {
		return false
	}
	//1235321

	rev := 0      // 只翻转后半段
	for x > rev { // 当 x <= rev 时，说明已经处理完一半数字
		rev = rev*10 + x%10
		x /= 10
	}

	// 偶数位：x == rev；奇数位：x == rev/10（中间位可忽略）
	return x == rev || x == rev/10
}

func isPalindrome(x int) bool {
	if x < 0 { // 负数一定不是回文
		return false
	}
	s := strconv.Itoa(x)
	for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
		if s[i] != s[j] {
			return false
		}
	}
	return true
}

/*
字符串
有效的括号

考察：字符串处理、栈的使用

题目：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效

链接：https://leetcode-cn.com/problems/valid-parentheses/

rune  是 Go 语言专门用来表示“一个 Unicode 码点”的整数类型，底层就是  int32  的别名

	Go 的  string  底层是字节序列（UTF-8 编码），一个中文字符可能占 3~4 个字节。
	如果直接用  byte （别名  uint8 ）遍历，会把多字节字符拆碎，得到乱码。
*/
func Taskthree(s string) bool {
	stack := []rune{}      // 用切片当栈
	pair := map[rune]rune{ // 右 -> 左
		')': '(',
		'}': '{',
		']': '[',
	}

	for _, ch := range s {
		if ch == '(' || ch == '{' || ch == '[' {
			stack = append(stack, ch) // 左括号入栈
		} else {
			// 当前是右括号，但栈已空 → 失败
			if len(stack) == 0 {
				return false
			}
			// 栈顶不匹配 → 失败
			if stack[len(stack)-1] != pair[ch] {
				return false
			}
			stack = stack[:len(stack)-1] // 匹配成功，弹出
		}
	}
	return len(stack) == 0 // 栈空才有效
}

/*
最长公共前缀

考察：字符串处理、循环嵌套

题目：查找字符串数组中的最长公共前缀

链接：https://leetcode-cn.com/problems/longest-common-prefix/
*/
/*
把数组看成一条“流水线”：
先用第 0 个串作为当前公共前缀  prefix ；
依次把  prefix  与后面的字符串求公共前缀；
当  prefix  变成空串时即可提前结束。
*/
func TaskFour(strs []string) string {
	if len(strs) == 0 {
		return ""
	}

	prefix := strs[0]
	for _, s := range strs[1:] {
		// 不断截断 prefix，直到它是 s 的前缀
		for !strings.HasPrefix(s, prefix) {
			if len(prefix) == 0 {
				return ""
			}
			prefix = prefix[:len(prefix)-1]
		}

	}

	return prefix

}

/*
基本值类型
加一

难度：简单

考察：数组操作、进位处理

题目：给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一

链接：https://leetcode-cn.com/problems/plus-one/
*/

/*

末位 9 + 1 = 10 → 本位写 0，向前进 1
次位 9 + 进位 1 = 10 → 本位写 0，再向前进 1
首位 2 + 进位 1 = 3 → 本位写 3，没有进位，结束
*/

func TaskFive(digits []int) []int {
    for i:=len(digits)-1; i>=0; i-- {
        if digits[i] < 9 {  // 当前位置不用进位，+1，然后直接返回
            digits[i]++
            return digits 
        } else {            // 要进位，当前位置置0
            digits[i] = 0
        }
    }
    return append([]int{1}, digits...)
}








/*
引用类型：切片
26. 删除有序数组中的重复项：给你一个有序数组 nums ，请你原地删除重复出现的元素，
使每个元素只出现一次，返回删除后数组的新长度。不要使用额外的数组空间，
你必须在原地修改输入数组并在使用 O(1)额外空间的条件下完成。
可以使用双指针法，一个慢指针 i 用于记录不重复元素的位置，一个快指针 j 用于遍历数组，
当 nums[i] 与 nums[j] 不相等时，
将 nums[j] 赋值给 nums[i + 1]，并将 i 后移一位。
链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/

*/

func TaskSix(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    i := 0 // 慢指针：已去重区间的末尾
    for j := 1; j < len(nums); j++ { // 快指针：探索下一个不同值
        if nums[j] != nums[i] {
            i++            // 新区间扩展一位
            nums[i] = nums[j] // 把新值放到 i+1 处
        }
    }
    return i + 1 // 长度 = 末尾索引 + 1
}







/*
. 合并区间：以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
可以先对区间数组按照区间的起始位置进行排序，然后使用一个切片来存储合并后的区间，
遍历排序后的区间数组，将当前区间与切片中最后一个区间进行比较，如果有重叠，则合并区间；
如果没有重叠，则将当前区间添加到切片中。
*/

/*
基础
两数之和

考察：数组遍历、map使用

题目：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数

链接：https://leetcode-cn.com/problems/two-sum/

*/

func TaskSevent(nums []int, target int) []int {
    m := make(map[int]int)          // value -> index
    for i, v := range nums {
        if j, ok := m[target-v]; ok {
            return []int{j, i}
        }
        m[v] = i
    }
    return nil
}